# -*- coding: utf-8 -*-
# @Time : 2024/2/20 9:33
# @Author : ZH
# @File : 105.py
# @Software: PyCharm
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or not inorder:
            return None

        # 前序遍历的第一个元素是根节点
        root_val = preorder[0]
        root = TreeNode(root_val)

        # 在中序遍历中找到根节点的索引
        root_index = inorder.index(root_val)

        # 根据中序遍历的划分，递归构建左子树和右子树
        root.left = self.buildTree(preorder[1:root_index + 1], inorder[:root_index])
        root.right = self.buildTree(preorder[root_index + 1:], inorder[root_index + 1:])

        return root



